package com.cqs.leetcode.string.sliding.windws;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author lixiaowen
 * @create 2019-12-16
 */
public class MinimumWindowSubstring76 {


    private Map<Character,Integer> targetMap = new HashMap<>();
    private Map<Character,Integer> sourceMap = new HashMap<>();

    public String minWindow(String s, String t) {
        if (s == null || t == null) return null;
        if (s.length() == 0 || t.length() == 0) return "";
        char[] schs = s.toCharArray();
        char[] tchs = t.toCharArray();
        for (char tch : tchs) {
            targetMap.put(tch,1 + targetMap.getOrDefault(tch,0));
        }
        int left  = -1; int right = 0;
        String result = "";
        for (int i = 0; i < schs.length; i++) {
            Character sch = schs[i];
            if (targetMap.containsKey(sch) ) {
                //找第一个可行解
                if (left == -1) left = i;
                sourceMap.put(sch,sourceMap.getOrDefault(sch,0) + 1);
                if (targetMap.size() == sourceMap.size()){
                    boolean find = true;
                    //判断所有的字符是否够了
                    //每个字符是否均足够
                    Set<Character> tKeys = targetMap.keySet();
                    for (Character tKey : tKeys) {
                        if (targetMap.get(tKey) > sourceMap.get(tKey)){
                            find = false;
                            break;
                        }
                    }
                    if (find){
                        right = i;
                        result = s.substring(left, right+1);
                        break;
                    }
                }
            }
        }
        //找到第一个可以行
        if ("".equals(result) || result.length() == t.length()) {
            return result;
        }

        //移动left指针
        while (left<=right){
            Integer sfre = sourceMap.get(schs[left]);
            while (left <= right && sfre == null){
                sfre = sourceMap.get(schs[++left]);
            }
            if (left>right || sfre.equals(targetMap.get(schs[left])) ) break;
            sourceMap.put(schs[left], sfre - 1);
            left++;
        }
        if (right - left + 1 < result.length()){
            result = s.substring(left,right+1);
        }

        //找下一个可行解
        while ( left <= right && right < s.length()){
            //移动right指针
            while (++right<s.length() && sourceMap.get(schs[right]) == null){

            }
            if (right >= s.length()) break;
            sourceMap.put(schs[right],sourceMap.get(schs[right]) + 1);
            //移动left指针
            while (left<=right){
                Integer sfre = sourceMap.get(schs[left]);
                while (left <= right && sfre == null){
                    sfre = sourceMap.get(schs[++left]);
                }
                if (left>right || sfre.equals(targetMap.get(schs[left])) ) break;
                sourceMap.put(schs[left], sfre - 1);
                left++;
            }
            if (right - left + 1 < result.length()){
                result = s.substring(left,right+1);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        MinimumWindowSubstring76 minWin = new MinimumWindowSubstring76();
        Map<String,String> cases =  new HashMap<>();
//        cases.put("ADOBECODEBANC","ABC");
//        cases.put("AAAABAA","A");
//        cases.put("","A");
////        cases.put("","");
//        cases.put("A","");
//        cases.put("AAA","AA");
//        cases.put("AA","AAA");
//        cases.put("1AAABBCS","BCS");
//        cases.put("AAABBCSS","BCSD");
//        cases.put("AAABBCSS","BCSD");
//        cases.put("cabwefgewcwaefgcf","ace");
        cases.put("bba","ab");
        cases.forEach((k,v)->{
            System.out.println(k +":" + v + " ==> " + minWin.minWindow(k,v));
        });
    }
}
